package codetop.huawei.T994;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: 18362
 * @Create: 2022-09-13 17:16:37 星期二
 */
class Solution {

    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

    public int orangesRotting(int[][] grid) {
        int[][] minDist = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++)
                minDist[i][j] = Integer.MAX_VALUE;
        }
        Deque<Integer> dqx = new LinkedList<>(), dqy = new LinkedList<>();
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    dqx.offer(i);
                    dqy.offer(j);
                    visited[i][j] = true;
                }
            }
        }
        int dist = 0;
        while (!dqx.isEmpty()) {
            int size = dqx.size();
            for (int i = 0; i < size; i++) {
                Integer x = dqx.poll(), y = dqy.poll();
                minDist[x][y] = dist;
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j], ny = y + dy[j];
                    if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length || grid[nx][ny] != 1 || visited[nx][ny])
                        continue;
                    visited[nx][ny] = true;
                    dqx.offer(nx);
                    dqy.offer(ny);
                }
            }
            dist++;
        }
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    if (minDist[i][j] == Integer.MAX_VALUE)
                        return -1;
                    res = Math.max(res, minDist[i][j]);
                }
            }
        }
        return res;
    }
}